/*************************************************************************
	> File Name: 234.回文链表.c
	> Author: Maureen 
	> Mail: Maureen@qq.com 
	> Created Time: 四  9/ 2 20:12:26 2021
 ************************************************************************/

#include <stdio.h>

//方法二：
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


bool isPalindrome(struct ListNode* head){
    //1.快慢指针找到链表中点
    struct ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        fast = fast->next->next;
        if (fast != NULL) slow = slow->next;
    }
    //此时slow为中点
    //2.翻转后半段
    struct ListNode *l = slow, *r = slow->next;
    l->next = NULL;
    while (r) {
        struct ListNode *temp = r->next;
        r->next = l;
        l = r;
        r = temp;
    }
    //3.双指针判断前后半段
    struct ListNode *p = head, *q = l;
    while (p && q) {
        if (p->val != q->val) return false;
        p = p->next;
        q = q->next;
    }
    return true;

}
